package com.xdja.kotlin

import java.util.*

/**
 * @author yuanwanli
 * @des   二叉树层平均
 * @date 2020/8/25
 */
fun main() {
    val treeNode4 = TreeNode(4)
    val treeNode5 = TreeNode(5)
    val treeNode6 = TreeNode(6)
    val treeNode2 = TreeNode(2)
    treeNode2.left=treeNode4
    treeNode2.right=treeNode5
    val treeNode3 = TreeNode(3)
    treeNode3.right=treeNode6
    val treeNode1 = TreeNode(1)
    treeNode1.right=treeNode3
    treeNode1.left=treeNode2
    val averageOfLayer = getAverageOfLayer(treeNode1)
    println(averageOfLayer)
}
fun getAverageOfLayer(node: TreeNode):List<Float>{
    val arrayDeque = ArrayDeque<TreeNode>()
    arrayDeque.add(node)
    var list= mutableListOf<Float>()
    while (arrayDeque.isNotEmpty()){
        var layervalue=0f
        var layerSize=arrayDeque.size
        for (index in 0 until layerSize){
            val poll = arrayDeque.poll()
            poll?.apply {
                layervalue+=value
                if (left!=null){
                    arrayDeque.add(left)
                }
                if (right!=null){
                    arrayDeque.add(right)
                }
            }
        }
        list.add(layervalue/layerSize)
    }
    return list
}
data class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}